package com.leetcode.程序员面试金典.hard;

import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2022-02-18 17:09
 */
public class 面试题_17_24_最大子矩阵 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[][] matrix = {
        {-1, -2, -9, 6},
        {8, -9, -3, -6},
        {2, 9, -7, -6}
    };
    int[] result = solution.getMaxMatrix(matrix);
    System.out.println(Arrays.toString(result));
  }

  static
  class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
      int r1 = 0;
      int c1 = 0;
      int r2 = 0;
      int c2 = 0;
      int max = Integer.MIN_VALUE;
      for (int i = 0; i < matrix.length; ++i) {
        int[] nums = new int[matrix[0].length];
        for (int j = i; j < matrix.length; ++j) {
          int lastSize = 0;
          int curR1 = 0;
          int curC1 = 0;
          for (int k = 0; k < nums.length; ++k) {
            nums[k] += matrix[j][k];
            if (lastSize <= 0) {
              lastSize = nums[k];
              curR1 = i;
              curC1 = k;
            } else {
              lastSize += nums[k];
            }

            if (lastSize > max) {
              max = lastSize;
              r1 = curR1;
              c1 = curC1;
              r2 = j;
              c2 = k;
            }
          }
        }
      }
      return new int[] {r1, c1, r2, c2};
    }
  }

}
